\contentsline {section}{\numberline {1}Introduction}{6}
\contentsline {subsection}{\numberline {1.1}Motivation}{6}
\contentsline {subsection}{\numberline {1.2}Content}{7}
\contentsline {section}{\numberline {2}Scheduling with and without Priority}{8}
\contentsline {subsection}{\numberline {2.1}Non-Preemptive Scheduling}{8}
\contentsline {subsection}{\numberline {2.2}Fixed-Priority Scheduling}{9}
\contentsline {subsubsection}{\numberline {2.2.1}Rate Monotonic Scheduling (RMS)}{9}
\contentsline {subsubsection}{\numberline {2.2.2}Deadline Monotonic Scheduling (DMS)}{10}
\contentsline {subsection}{\numberline {2.3}Dynamic-Priority Scheduling}{10}
\contentsline {subsubsection}{\numberline {2.3.1}Earliest Deadline First (EDF)}{11}
\contentsline {subsubsection}{\numberline {2.3.2}Least Slack Time First (LST)}{13}
\contentsline {subsection}{\numberline {2.4}ASAP and ALAP Scheduling}{14}
\contentsline {section}{\numberline {3}Design Space Exploration Framework}{16}
\contentsline {subsection}{\numberline {3.1}Organization and Structure}{16}
\contentsline {subsubsection}{\numberline {3.1.1}Application and Architecture Modeling}{18}
\contentsline {subsubsection}{\numberline {3.1.2}Mapping}{18}
\contentsline {subsubsection}{\numberline {3.1.3}Evaluation}{19}
\contentsline {subsubsection}{\numberline {3.1.4}Guidance}{20}
\contentsline {subsection}{\numberline {3.2}Scheduling}{20}
\contentsline {section}{\numberline {4}New Dynamic-Priority Scheduling}{25}
\contentsline {subsection}{\numberline {4.1}Deadline and Latency}{25}
\contentsline {subsection}{\numberline {4.2}Scheduling via the Max-Plus Algorithm}{26}
\contentsline {subsubsection}{\numberline {4.2.1}Longest Path}{26}
\contentsline {subsubsection}{\numberline {4.2.2}Scheduling}{28}
\contentsline {subsection}{\numberline {4.3}Dijkstra Algorithm}{32}
\contentsline {subsection}{\numberline {4.4}Best Case, Average Case and Worst Case}{34}
\contentsline {subsection}{\numberline {4.5}Class Structure}{38}
\contentsline {section}{\numberline {5}Comparison Result}{41}
\contentsline {subsection}{\numberline {5.1}Benchmark}{41}
\contentsline {subsection}{\numberline {5.2}Max-Plus Algorithm vs. Dijkstra Algorithm}{42}
\contentsline {subsection}{\numberline {5.3}Prioritized Deadline}{43}
\contentsline {subsection}{\numberline {5.4}Fixed-Priority vs. Dynamic-Priority Scheduling}{44}
\contentsline {subsection}{\numberline {5.5}New vs. Traditional Dynamic-Priority Scheduling}{46}
\contentsline {subsection}{\numberline {5.6}Summary}{47}
\contentsline {section}{\numberline {6}Conclusion and Future Work}{49}
